package algorithm;

/**
 * Created by baoyunfeng on 2018/1/10.
 */
public class UnionFind {
    Node[] node;

    //并查集中的节点
    private class Node{
        int parent;
        boolean root;

        private Node(){
            parent = 1;
            root = true;
        }
    }

    //将每个元素初始化为一颗单节点树
    public UnionFind(int n){
        node = new Node[n+1];
        for(int i = 0 ;i<= n;i++){
            node[i] = new Node();
        }
    }

    //从某个元素节点走到树根处，找出所在集合的名字
    public int find(int i){
        while(!node[i].root){
            i = node[i].parent;
        }
        return i;
    }

    //合并
    public void union(int a, int b){
        node[a].parent += node[b].parent;
        node[b].root = false;
        node[b].parent = a;
    }

    //快速合并
    //将表示小树的树根改为表示大叔的树根的儿子节点
    public void quicklyUnion(int a, int b){
        if(node[a].parent < node[b].parent){
            node[b].parent += node[a].parent;
            node[a].root = false;
            node[a].parent = a;
        }else{
            node[a].parent += node[b].parent;
            node[b].root = false;
            node[b].parent = a;
        }
    }

    //路径压缩技术



}
